home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / info-service / www / src / midaswww-1.0 / Tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-11-16  |  29.2 KB  |  1,046 lines
  1. /*
  2.  * $XConsortium: Tree.c,v 1.42 91/02/20 20:06:07 converse Exp $
  3.  *
  4.  * Copyright 1990 Massachusetts Institute of Technology
  5.  * Copyright 1989 Prentice Hall
  6.  *
  7.  * Permission to use, copy, modify, and distribute this software for any
  8.  * purpose and without fee is hereby granted, provided that the above
  9.  * copyright notice appear in all copies and that both the copyright notice
  10.  * and this permission notice appear in supporting documentation.
  11.  * 
  12.  * M.I.T., Prentice Hall and the authors disclaim all warranties with regard
  13.  * to this software, including all implied warranties of merchantability and
  14.  * fitness.  In no event shall M.I.T., Prentice Hall or the authors be liable
  15.  * for any special, indirect or cosequential damages or any damages whatsoever
  16.  * resulting from loss of use, data or profits, whether in an action of
  17.  * contract, negligence or other tortious action, arising out of or in
  18.  * connection with the use or performance of this software.
  19.  * 
  20.  * Authors:  Jim Fulton, MIT X Consortium,
  21.  *           based on a version by Douglas Young, Prentice Hall
  22.  * 
  23.  * This widget is based on the Tree widget described on pages 397-419 of
  24.  * Douglas Young's book "The X Window System, Programming and Applications 
  25.  * with Xt OSF/Motif Edition."  The layout code has been rewritten to use
  26.  * additional blank space to make the structure of the graph easier to see
  27.  * as well as to support vertical trees.
  28.  */
  29.  
  30. #include <X11/Intrinsic.h>
  31. #include <X11/IntrinsicP.h>
  32. #include <X11/StringDefs.h>
  33. #include <X11/CoreP.h>
  34. #include <X11/CompositeP.h>
  35. #include <X11/ConstrainP.h>
  36. #include "TreeP.h"
  37.  
  38. #define IsHorizontal(tw) ((tw)->tree.gravity == WestGravity || \
  39.               (tw)->tree.gravity == EastGravity)
  40.  
  41.  
  42.                     /* widget class method */
  43. static void             ClassInitialize();
  44. static void             Initialize();
  45. static void             ConstraintInitialize();
  46. static void             ConstraintDestroy();
  47. static Boolean          ConstraintSetValues();
  48. static void             Destroy();
  49. static Boolean          SetValues();
  50. static XtGeometryResult GeometryManager();
  51. static void             ChangeManaged();
  52. static void             Redisplay();
  53. static XtGeometryResult    QueryGeometry();
  54.  
  55.                     /* utility routines */
  56. static void             insert_node();
  57. static void             delete_node();
  58. static void             layout_tree();
  59.  
  60.  
  61. /*
  62.  * resources of the tree itself
  63.  */
  64. static XtResource resources[] = {
  65.     { XtNautoReconfigure, XtCAutoReconfigure, XtRBoolean, sizeof (Boolean),
  66.     XtOffsetOf(TreeRec, tree.auto_reconfigure), XtRImmediate,
  67.     (XtPointer) FALSE },
  68.     { XtNhSpace, XtCHSpace, XtRDimension, sizeof (Dimension),
  69.     XtOffsetOf(TreeRec, tree.hpad), XtRImmediate, (XtPointer) 0 },
  70.     { XtNvSpace, XtCVSpace, XtRDimension, sizeof (Dimension),
  71.     XtOffsetOf(TreeRec, tree.vpad), XtRImmediate, (XtPointer) 0 },
  72.     { XtNforeground, XtCForeground, XtRPixel, sizeof (Pixel),
  73.     XtOffsetOf(TreeRec, tree.foreground), XtRString,
  74.     XtDefaultForeground},
  75.     { XtNlineWidth, XtCLineWidth, XtRDimension, sizeof (Dimension),
  76.     XtOffsetOf(TreeRec, tree.line_width), XtRImmediate, (XtPointer) 0 },
  77.     { XtNgravity, XtCGravity, XtRGravity, sizeof (XtGravity),
  78.     XtOffsetOf(TreeRec, tree.gravity), XtRImmediate,
  79.     (XtPointer) WestGravity },
  80. };
  81.  
  82.  
  83. /*
  84.  * resources that are attached to all children of the tree
  85.  */
  86. static XtResource treeConstraintResources[] = {
  87.     { XtNtreeParent, XtCTreeParent, XtRWidget, sizeof (Widget),
  88.     XtOffsetOf(TreeConstraintsRec, tree.parent), XtRImmediate, NULL },
  89.     { XtNtreeGC, XtCTreeGC, XtRGC, sizeof(GC),
  90.     XtOffsetOf(TreeConstraintsRec, tree.gc), XtRImmediate, NULL },
  91. };
  92.  
  93.  
  94. TreeClassRec treeClassRec = {
  95.   {
  96.                     /* core_class fields  */
  97.     (WidgetClass) &constraintClassRec,  /* superclass         */
  98.     "Tree",                /* class_name         */
  99.     sizeof(TreeRec),            /* widget_size        */
  100.     ClassInitialize,            /* class_init         */
  101.     NULL,                /* class_part_init    */
  102.     FALSE,                /* class_inited       */    
  103.     Initialize,                /* initialize         */
  104.     NULL,                /* initialize_hook    */    
  105.     XtInheritRealize,            /* realize            */
  106.     NULL,                /* actions            */
  107.     0,                    /* num_actions        */    
  108.     resources,                /* resources          */
  109.     XtNumber(resources),        /* num_resources      */
  110.     NULLQUARK,                /* xrm_class          */
  111.     TRUE,                /* compress_motion    */    
  112.     TRUE,                /* compress_exposure  */    
  113.     TRUE,                /* compress_enterleave*/    
  114.     TRUE,                /* visible_interest   */
  115.     Destroy,                /* destroy            */
  116.     NULL,                /* resize             */
  117.     Redisplay,                /* expose             */
  118.     SetValues,                /* set_values         */
  119.     NULL,                /* set_values_hook    */    
  120.     XtInheritSetValuesAlmost,        /* set_values_almost  */
  121.     NULL,                /* get_values_hook    */    
  122.     NULL,                /* accept_focus       */
  123.     XtVersion,                /* version            */    
  124.     NULL,                /* callback_private   */
  125.     NULL,                /* tm_table           */
  126.     QueryGeometry,            /* query_geometry     */    
  127.     NULL,                /* display_accelerator*/
  128.     NULL,                /* extension          */
  129.   },
  130.   {
  131.                     /* composite_class fields */
  132.     GeometryManager,            /* geometry_manager    */
  133.     ChangeManaged,            /* change_managed      */
  134.     XtInheritInsertChild,        /* insert_child        */    
  135.     XtInheritDeleteChild,        /* delete_child        */    
  136.     NULL,                /* extension           */
  137.   },
  138.   { 
  139.                     /* constraint_class fields */
  140.    treeConstraintResources,        /* subresources        */
  141.    XtNumber(treeConstraintResources),    /* subresource_count   */
  142.    sizeof(TreeConstraintsRec),        /* constraint_size     */
  143.    ConstraintInitialize,        /* initialize          */
  144.    ConstraintDestroy,            /* destroy             */
  145.    ConstraintSetValues,            /* set_values          */
  146.    NULL,                /* extension           */
  147.    },
  148.   {
  149.                     /* Tree class fields */
  150.     0,                    /* ignore              */    
  151.   }
  152. };
  153.  
  154. WidgetClass treeWidgetClass = (WidgetClass) &treeClassRec;
  155.  
  156.  
  157. /*****************************************************************************
  158.  *                                                                           *
  159.  *                 tree utility routines                           *
  160.  *                                                                           *
  161.  *****************************************************************************/
  162.  
  163. static void initialize_dimensions (listp, sizep, n)
  164.     Dimension **listp;
  165.     int *sizep;
  166.     int n;
  167. {
  168.     register int i;
  169.     register Dimension *l;
  170.  
  171.     if (!*listp) {
  172.     *listp = (Dimension *) XtCalloc ((unsigned int) n,
  173.                      (unsigned int) sizeof(Dimension));
  174.     *sizep = ((*listp) ? n : 0);
  175.     return;
  176.     }
  177.     if (n > *sizep) {
  178.     *listp = (Dimension *) XtRealloc((char *) *listp,
  179.                      (unsigned int) (n*sizeof(Dimension)));
  180.     if (!*listp) {
  181.         *sizep = 0;
  182.         return;
  183.     }
  184.     for (i = *sizep, l = (*listp) + i; i < n; i++, l++) *l = 0;
  185.     *sizep = n;
  186.     }
  187.     return;
  188. }
  189.  
  190. static GC get_tree_gc (w)
  191.     TreeWidget w;
  192. {
  193.     XtGCMask valuemask = GCBackground | GCForeground;
  194.     XGCValues values;
  195.  
  196.     values.background = w->core.background_pixel;
  197.     values.foreground = w->tree.foreground;
  198.     if (w->tree.line_width != 0) {
  199.     valuemask |= GCLineWidth;
  200.     values.line_width = w->tree.line_width;
  201.     }
  202.  
  203.     return XtGetGC ((Widget) w, valuemask, &values);
  204. }
  205.  
  206. static void insert_node (parent, node)
  207.      Widget parent, node;
  208. {
  209.     TreeConstraints pc;
  210.     TreeConstraints nc = TREE_CONSTRAINT(node);
  211.     int nindex;
  212.   
  213.     nc->tree.parent = parent;
  214.  
  215.     if (parent == NULL) return;
  216.  
  217.     /*
  218.      * If there isn't more room in the children array, 
  219.      * allocate additional space.
  220.      */  
  221.     pc = TREE_CONSTRAINT(parent);
  222.     nindex = pc->tree.n_children;
  223.   
  224.     if (pc->tree.n_children == pc->tree.max_children) {
  225.     pc->tree.max_children += (pc->tree.max_children / 2) + 2;
  226.     pc->tree.children = (WidgetList) XtRealloc ((char *)pc->tree.children, 
  227.                             (unsigned int)
  228.                             ((pc->tree.max_children) *
  229.                             sizeof(Widget)));
  230.     } 
  231.  
  232.     /*
  233.      * Add the sub_node in the next available slot and 
  234.      * increment the counter.
  235.      */
  236.     pc->tree.children[nindex] = node;
  237.     pc->tree.n_children++;
  238. }
  239.  
  240. static void delete_node (parent, node)
  241.     Widget parent, node;
  242. {
  243.     TreeConstraints pc;
  244.     int pos, i;
  245.  
  246.     /*
  247.      * Make sure the parent exists.
  248.      */
  249.     if (!parent) return;  
  250.   
  251.     pc = TREE_CONSTRAINT(parent);
  252.  
  253.     /*
  254.      * Find the sub_node on its parent's list.
  255.      */
  256.     for (pos = 0; pos < pc->tree.n_children; pos++)
  257.       if (pc->tree.children[pos] == node) break;
  258.  
  259.     if (pos == pc->tree.n_children) return;
  260.  
  261.     /*
  262.      * Decrement the number of children
  263.      */  
  264.     pc->tree.n_children--;
  265.  
  266.     /*
  267.      * Fill in the gap left by the sub_node.
  268.      * Zero the last slot for good luck.
  269.      */
  270.     for (i = pos; i < pc->tree.n_children; i++) 
  271.       pc->tree.children[i] = pc->tree.children[i+1];
  272.  
  273.     pc->tree.children[pc->tree.n_children]=0;
  274. }
  275.  
  276. static void check_gravity (tw, grav)
  277.     TreeWidget tw;
  278.     XtGravity grav;
  279. {
  280.     switch (tw->tree.gravity) {
  281.       case WestGravity: case NorthGravity: case EastGravity: case SouthGravity:
  282.     break;
  283.       default:
  284.     tw->tree.gravity = grav;
  285.     break;
  286.     }
  287. }
  288. #define done(address, type) \
  289.         { (*toVal).size = sizeof(type); (*toVal).addr = (caddr_t) address; }
  290.  
  291. static struct _namepair {
  292.     XrmQuark quark;
  293.     char *name;
  294.     XtGravity gravity;
  295. } names[] = {
  296.     { NULLQUARK, XtEForget, ForgetGravity },
  297.     { NULLQUARK, XtENorthWest, NorthWestGravity },
  298.     { NULLQUARK, XtENorth, NorthGravity },
  299.     { NULLQUARK, XtENorthEast, NorthEastGravity },
  300.     { NULLQUARK, XtEWest, WestGravity },
  301.     { NULLQUARK, XtECenter, CenterGravity },
  302.     { NULLQUARK, XtEEast, EastGravity },
  303.     { NULLQUARK, XtESouthWest, SouthWestGravity },
  304.     { NULLQUARK, XtESouth, SouthGravity },
  305.     { NULLQUARK, XtESouthEast, SouthEastGravity },
  306.     { NULLQUARK, XtEStatic, StaticGravity },
  307.     { NULLQUARK, XtEUnmap, UnmapGravity },
  308.     { NULLQUARK, XtEleft, WestGravity },
  309.     { NULLQUARK, XtEtop, NorthGravity },
  310.     { NULLQUARK, XtEright, EastGravity },
  311.     { NULLQUARK, XtEbottom, SouthGravity },
  312.     { NULLQUARK, NULL, ForgetGravity }
  313. };
  314.  
  315. void CvtStringToGravity (args, num_args, fromVal, toVal)
  316.     XrmValuePtr args;
  317.     Cardinal    *num_args;
  318.     XrmValuePtr fromVal;
  319.     XrmValuePtr toVal;
  320. {
  321.     static Boolean haveQuarks = FALSE;
  322.     char lowerName[40];
  323.     XrmQuark q;
  324.     char *s, *t;
  325.     struct _namepair *np;
  326.  
  327.     if (*num_args != 0)
  328.         XtWarningMsg("wrongParameters","cvtStringToGravity","XtToolkitError",
  329.                   "String to Gravity conversion needs no extra arguments",
  330.                   (String *) NULL, (Cardinal *)NULL);
  331.  
  332.     if (!haveQuarks) {
  333.     for (np = names; np->name; np++) {
  334.         np->quark = XrmStringToQuark (np->name);
  335.     }
  336.     haveQuarks = TRUE;
  337.     }
  338.  
  339.     s = (char *) fromVal->addr;
  340.     if (strlen(s) < sizeof lowerName) {
  341.     for (t=lowerName;  (*t++ = tolower(*s++)) != '\0'; );
  342.     q = XrmStringToQuark (lowerName);
  343.  
  344.     for (np = names; np->name; np++) {
  345.         if (np->quark == q) {
  346.         done (&np->gravity, XtGravity);
  347.         return;
  348.         }
  349.     }
  350.     }
  351.     XtStringConversionWarning((char *) fromVal->addr, XtRGravity);
  352. }
  353.  
  354.  
  355.  
  356.  
  357.  
  358. /*****************************************************************************
  359.  *                                                                           *
  360.  *                   tree class methods                             *
  361.  *                                                                           *
  362.  *****************************************************************************/
  363.  
  364. static void ClassInitialize ()
  365. {
  366.     XtAddConverter (XtRString, XtRGravity, CvtStringToGravity,
  367.                 (XtConvertArgList) NULL, (Cardinal) 0);
  368. }
  369.  
  370.  
  371. static void Initialize (grequest, gnew)
  372.     Widget grequest, gnew;
  373. {
  374.     TreeWidget request = (TreeWidget) grequest, new = (TreeWidget) gnew;
  375.     Arg args[2];
  376.  
  377.     /*
  378.      * Make sure the widget's width and height are 
  379.      * greater than zero.
  380.      */
  381.     if (request->core.width <= 0) new->core.width = 5;
  382.     if (request->core.height <= 0) new->core.height = 5;
  383.  
  384.     /*
  385.      * Set the padding according to the orientation
  386.      */
  387.     if (request->tree.hpad == 0 && request->tree.vpad == 0) {
  388.     if (IsHorizontal (request)) {
  389.         new->tree.hpad = TREE_HORIZONTAL_DEFAULT_SPACING;
  390.         new->tree.vpad = TREE_VERTICAL_DEFAULT_SPACING;
  391.     } else {
  392.         new->tree.hpad = TREE_VERTICAL_DEFAULT_SPACING;
  393.         new->tree.vpad = TREE_HORIZONTAL_DEFAULT_SPACING;
  394.     }
  395.     }
  396.  
  397.     /*
  398.      * Create a graphics context for the connecting lines.
  399.      */
  400.     new->tree.gc = get_tree_gc (new);
  401.  
  402.     /*
  403.      * Create the hidden root widget.
  404.      */
  405.     new->tree.tree_root = (Widget) NULL;
  406.     XtSetArg(args[0], XtNwidth, 1);
  407.     XtSetArg(args[1], XtNheight, 1);
  408.     new->tree.tree_root = XtCreateWidget ("root", widgetClass, gnew, args,((Cardinal) 2));
  409.     
  410.     /*
  411.      * Allocate the array used to hold the widest values per depth
  412.      */
  413.     new->tree.largest = NULL;
  414.     new->tree.n_largest = 0;
  415.     initialize_dimensions (&new->tree.largest, &new->tree.n_largest, 
  416.                TREE_INITIAL_DEPTH);
  417.  
  418.     /*
  419.      * make sure that our gravity is one of the acceptable values
  420.      */
  421.     check_gravity (new, WestGravity);
  422. } 
  423.  
  424.  
  425. /* ARGSUSED */
  426. static void ConstraintInitialize (request, new)
  427.      Widget request, new;
  428. {
  429.     TreeConstraints tc = TREE_CONSTRAINT(new);
  430.     TreeWidget tw = (TreeWidget) new->core.parent;
  431.  
  432.     /*
  433.      * Initialize the widget to have no sub-nodes.
  434.      */
  435.     tc->tree.n_children = 0;
  436.     tc->tree.max_children = 0;
  437.     tc->tree.children = (Widget *) NULL;
  438.     tc->tree.x = tc->tree.y = 0; 
  439.     tc->tree.bbsubwidth = 0;
  440.     tc->tree.bbsubheight = 0;
  441.  
  442.  
  443.     /*
  444.      * If this widget has a super-node, add it to that 
  445.      * widget' sub-nodes list. Otherwise make it a sub-node of 
  446.      * the tree_root widget.
  447.      */
  448.     if (tc->tree.parent)
  449.       insert_node (tc->tree.parent, new);
  450.     else if (tw->tree.tree_root)
  451.       insert_node (tw->tree.tree_root, new);
  452. } 
  453.  
  454.  
  455. /* ARGSUSED */
  456. static Boolean SetValues (gcurrent, grequest, gnew)
  457.     Widget gcurrent, grequest, gnew;
  458. {
  459.     TreeWidget current = (TreeWidget) gcurrent, new = (TreeWidget) gnew;
  460.     Boolean redraw = FALSE;
  461.  
  462.     /*
  463.      * If the foreground color has changed, redo the GC's
  464.      * and indicate a redraw.
  465.      */
  466.     if (new->tree.foreground != current->tree.foreground ||
  467.     new->core.background_pixel != current->core.background_pixel ||
  468.     new->tree.line_width != current->tree.line_width) {
  469.     XtReleaseGC (gnew, new->tree.gc);
  470.     new->tree.gc = get_tree_gc (new);
  471.     redraw = TRUE;     
  472.     }
  473.  
  474.     /*
  475.      * If the minimum spacing has changed, recalculate the
  476.      * tree layout. layout_tree() does a redraw, so we don't
  477.      * need SetValues to do another one.
  478.      */
  479.     if (new->tree.gravity != current->tree.gravity) {
  480.     check_gravity (new, current->tree.gravity);
  481.     }
  482.  
  483.     if (IsHorizontal(new) != IsHorizontal(current)) {
  484.     if (new->tree.vpad == current->tree.vpad &&
  485.         new->tree.hpad == current->tree.hpad) {
  486.         new->tree.vpad = current->tree.hpad;
  487.         new->tree.hpad = current->tree.vpad;
  488.     }
  489.     }
  490.  
  491.     if (new->tree.vpad != current->tree.vpad ||
  492.     new->tree.hpad != current->tree.hpad ||
  493.     new->tree.gravity != current->tree.gravity) {
  494.     layout_tree (new, TRUE);
  495.     redraw = FALSE;
  496.     }
  497.     return redraw;
  498. }
  499.  
  500.  
  501. /* ARGSUSED */
  502. static Boolean ConstraintSetValues (current, request, new, args, num_args)
  503.     Widget current, request, new;
  504.     ArgList args;
  505.     Cardinal *num_args;
  506. {
  507.     TreeConstraints newc = TREE_CONSTRAINT(new);
  508.     TreeConstraints curc = TREE_CONSTRAINT(current);
  509.     TreeWidget tw = (TreeWidget) new->core.parent;
  510.  
  511.     /*
  512.      * If the parent field has changed, remove the widget
  513.      * from the old widget's children list and add it to the
  514.      * new one.
  515.      */
  516.     if (curc->tree.parent != newc->tree.parent){
  517.     if (curc->tree.parent)
  518.       delete_node (curc->tree.parent, new);
  519.     if (newc->tree.parent)
  520.       insert_node(newc->tree.parent, new);
  521.  
  522.     /*
  523.      * If the Tree widget has been realized, 
  524.      * compute new layout.
  525.      */
  526.     if (XtIsRealized((Widget)tw))
  527.       layout_tree (tw, FALSE);
  528.     }
  529.     return False;
  530. }
  531.  
  532.  
  533. static void ConstraintDestroy (w) 
  534.     Widget w;
  535. { 
  536.     TreeConstraints tc = TREE_CONSTRAINT(w);
  537.     TreeWidget tw = (TreeWidget) XtParent(w);
  538.     int i;
  539.  
  540.     /* 
  541.      * Remove the widget from its parent's sub-nodes list and
  542.      * make all this widget's sub-nodes sub-nodes of the parent.
  543.      */
  544.   
  545.     if (tw->tree.tree_root == w) {
  546.     if (tc->tree.n_children > 0)
  547.       tw->tree.tree_root = tc->tree.children[0];
  548.     else
  549.       tw->tree.tree_root = NULL;
  550.     }
  551.  
  552.     delete_node (tc->tree.parent, (Widget) w);
  553.     for (i = 0; i< tc->tree.n_children; i++)
  554.       insert_node (tc->tree.parent, tc->tree.children[i]);
  555.  
  556.     layout_tree ((TreeWidget) (w->core.parent), FALSE);
  557. }
  558.  
  559. /* ARGSUSED */
  560. static XtGeometryResult GeometryManager (w, request, reply)
  561.     Widget w;
  562.     XtWidgetGeometry *request;
  563.     XtWidgetGeometry *reply;
  564. {
  565.  
  566.     TreeWidget tw = (TreeWidget) w->core.parent;
  567.  
  568.     /*
  569.      * No position changes allowed!.
  570.      */
  571.     if ((request->request_mode & CWX && request->x!=w->core.x)
  572.     ||(request->request_mode & CWY && request->y!=w->core.y))
  573.       return (XtGeometryNo);
  574.  
  575.     /*
  576.      * Allow all resize requests.
  577.      */
  578.  
  579.     if (request->request_mode & CWWidth)
  580.       w->core.width = request->width;
  581.     if (request->request_mode & CWHeight)
  582.       w->core.height = request->height;
  583.     if (request->request_mode & CWBorderWidth)
  584.       w->core.border_width = request->border_width;
  585.  
  586.     if (tw->tree.auto_reconfigure) layout_tree (tw, FALSE);
  587.     return (XtGeometryYes);
  588. }
  589.  
  590. static void ChangeManaged (gw)
  591.     Widget gw;
  592. {
  593.     layout_tree ((TreeWidget) gw, FALSE);
  594. }
  595.  
  596.  
  597. static void Destroy (gw)
  598.     Widget gw;
  599. {
  600.     TreeWidget w = (TreeWidget) gw;
  601.  
  602.     XtReleaseGC (gw, w->tree.gc);
  603.     if (w->tree.largest) XtFree ((char *) w->tree.largest);
  604. }
  605.  
  606.  
  607. /* ARGSUSED */
  608. static void Redisplay (tw, event, region)
  609.      TreeWidget tw;
  610.      XEvent *event;
  611.      Region region;
  612. {
  613.     /*
  614.      * If the Tree widget is visible, visit each managed child.
  615.      */
  616.     if (tw->core.visible) {
  617.     int i, j;
  618.     Display *dpy = XtDisplay (tw);
  619.     Window w = XtWindow (tw);
  620.  
  621.     for (i = 0; i < tw->composite.num_children; i++) {
  622.         register Widget child = tw->composite.children[i];
  623.         TreeConstraints tc = TREE_CONSTRAINT(child);
  624.  
  625.         /*
  626.          * Don't draw lines from the fake tree_root.
  627.          */
  628.         if (child != tw->tree.tree_root && tc->tree.n_children) {
  629.         int srcx = child->core.x + child->core.border_width;
  630.         int srcy = child->core.y + child->core.border_width;
  631.  
  632.         switch (tw->tree.gravity) {
  633.           case WestGravity:
  634.             srcx += child->core.width + child->core.border_width;
  635.             /* fall through */
  636.           case EastGravity:
  637.             srcy += child->core.height / 2;
  638.             break;
  639.  
  640.           case NorthGravity:
  641.             srcy += child->core.height + child->core.border_width;
  642.             /* fall through */
  643.           case SouthGravity:
  644.             srcx += child->core.width / 2;
  645.             break;
  646.         }
  647.  
  648.         for (j = 0; j < tc->tree.n_children; j++) {
  649.             register Widget k = tc->tree.children[j];
  650.             GC gc = (tc->tree.gc ? tc->tree.gc : tw->tree.gc);
  651.  
  652.             switch (tw->tree.gravity) {
  653.               case WestGravity:
  654.             /*
  655.              * right center to left center
  656.              */
  657.             XDrawLine (dpy, w, gc, srcx, srcy,
  658.                    (int) k->core.x,
  659.                    (k->core.y + ((int) k->core.border_width) +
  660.                     ((int) k->core.height) / 2));
  661.             break;
  662.  
  663.               case NorthGravity:
  664.             /*
  665.              * bottom center to top center
  666.              */
  667.             XDrawLine (dpy, w, gc, srcx, srcy,
  668.                    (k->core.x + ((int) k->core.border_width) +
  669.                     ((int) k->core.width) / 2),
  670.                    (int) k->core.y);
  671.             break;
  672.  
  673.               case EastGravity:
  674.             /*
  675.              * left center to right center
  676.              */
  677.             XDrawLine (dpy, w, gc, srcx, srcy,
  678.                    (k->core.x +
  679.                     (((int) k->core.border_width) << 1) +
  680.                     (int) k->core.width),
  681.                    (k->core.y + ((int) k->core.border_width) +
  682.                     ((int) k->core.height) / 2));
  683.             break;
  684.  
  685.               case SouthGravity:
  686.             /*
  687.              * top center to bottom center
  688.              */
  689.             XDrawLine (dpy, w, gc, srcx, srcy,
  690.                    (k->core.x + ((int) k->core.border_width) +
  691.                     ((int) k->core.width) / 2),
  692.                    (k->core.y +
  693.                     (((int) k->core.border_width) << 1) +
  694.                     (int) k->core.height));
  695.             break;
  696.             }
  697.         }
  698.         }
  699.     }
  700.     }
  701. }
  702.  
  703. static XtGeometryResult QueryGeometry (w, intended, preferred)
  704.     Widget w;
  705.     XtWidgetGeometry *intended, *preferred;
  706. {
  707.     register TreeWidget tw = (TreeWidget) w;
  708.  
  709.     preferred->request_mode = (CWWidth | CWHeight);
  710.     preferred->width = tw->tree.maxwidth;
  711.     preferred->height = tw->tree.maxheight;
  712.  
  713.     if (((intended->request_mode & (CWWidth | CWHeight)) ==
  714.      (CWWidth | CWHeight)) &&
  715.     intended->width == preferred->width &&
  716.     intended->height == preferred->height)
  717.       return XtGeometryYes;
  718.     else if (preferred->width == w->core.width &&
  719.              preferred->height == w->core.height)
  720.       return XtGeometryNo;
  721.     else
  722.       return XtGeometryAlmost;
  723. }
  724.  
  725.  
  726. /*****************************************************************************
  727.  *                                                                           *
  728.  *                 tree layout algorithm                           *
  729.  *                                                                           *
  730.  * Each node in the tree is "shrink-wrapped" with a minimal bounding         *
  731.  * rectangle, laid next to its siblings (with a small about of padding in    *
  732.  * between) and then wrapped with their parent.  Parents are centered about  *
  733.  * their children (or vice versa if the parent is larger than the children). *
  734.  *                                                                           *
  735.  *****************************************************************************/
  736.  
  737. static void compute_bounding_box_subtree (tree, w, depth)
  738.     TreeWidget tree;
  739.     Widget w;
  740.     int depth;
  741. {
  742.     TreeConstraints tc = TREE_CONSTRAINT(w);  /* info attached to all kids */
  743.     register int i;
  744.     Bool horiz = IsHorizontal (tree);
  745.     Dimension newwidth, newheight;
  746.     Dimension bw2 = w->core.border_width * 2;
  747.  
  748.     /*
  749.      * Set the max-size per level.
  750.      */
  751.     if (depth >= tree->tree.n_largest) {
  752.     initialize_dimensions (&tree->tree.largest,
  753.                    &tree->tree.n_largest, depth + 1);
  754.     }
  755.     newwidth = ((horiz ? w->core.width : w->core.height) + bw2);
  756.     if (tree->tree.largest[depth] < newwidth)
  757.       tree->tree.largest[depth] = newwidth;
  758.  
  759.  
  760.     /*
  761.      * initialize
  762.      */
  763.     tc->tree.bbwidth = w->core.width + bw2;
  764.     tc->tree.bbheight = w->core.height + bw2;
  765.  
  766.     if (tc->tree.n_children == 0) return;
  767.  
  768.     /*
  769.      * Figure the size of the opposite dimension (vertical if tree is 
  770.      * horizontal, else vice versa).  The other dimension will be set 
  771.      * in the second pass once we know the maximum dimensions.
  772.      */
  773.     newwidth = 0;
  774.     newheight = 0;
  775.     for (i = 0; i < tc->tree.n_children; i++) {
  776.     Widget child = tc->tree.children[i];
  777.     TreeConstraints cc = TREE_CONSTRAINT(child);
  778.         
  779.     compute_bounding_box_subtree (tree, child, depth + 1);
  780.  
  781.     if (horiz) {
  782.         if (newwidth < cc->tree.bbwidth) newwidth = cc->tree.bbwidth;
  783.         newheight += tree->tree.vpad + cc->tree.bbheight;
  784.     } else {
  785.         if (newheight < cc->tree.bbheight) newheight = cc->tree.bbheight;
  786.         newwidth += tree->tree.hpad + cc->tree.bbwidth;
  787.     }
  788.     }
  789.  
  790.  
  791.     tc->tree.bbsubwidth = newwidth;
  792.     tc->tree.bbsubheight = newheight;
  793.  
  794.     /*
  795.      * Now fit parent onto side (or top) of bounding box and correct for
  796.      * extra padding.  Be careful of unsigned arithmetic.
  797.      */
  798.     if (horiz) {
  799.     tc->tree.bbwidth += tree->tree.hpad + newwidth;
  800.     newheight -= tree->tree.vpad;
  801.     if (newheight > tc->tree.bbheight) tc->tree.bbheight = newheight;
  802.     } else {
  803.     tc->tree.bbheight += tree->tree.vpad + newheight;
  804.     newwidth -= tree->tree.hpad;
  805.     if (newwidth > tc->tree.bbwidth) tc->tree.bbwidth = newwidth;
  806.     }
  807. }
  808.  
  809.  
  810. static void set_positions (tw, w, level)
  811.      TreeWidget tw;
  812.      Widget w;
  813.      int level;
  814. {
  815.     int i;
  816.   
  817.     if (w) {
  818.     TreeConstraints tc = TREE_CONSTRAINT(w);
  819.  
  820.     if (level > 0) {
  821.         /*
  822.          * mirror if necessary
  823.          */
  824.         switch (tw->tree.gravity) {
  825.           case EastGravity:
  826.         tc->tree.x = (((Position) tw->tree.maxwidth) -
  827.                   ((Position) w->core.width) - tc->tree.x);
  828.         break;
  829.  
  830.           case SouthGravity:
  831.         tc->tree.y = (((Position) tw->tree.maxheight) -
  832.                   ((Position) w->core.height) - tc->tree.y);
  833.         break;
  834.         }
  835.  
  836.         /*
  837.          * Move the widget into position.
  838.          */
  839.         XtMoveWidget (w, tc->tree.x, tc->tree.y);
  840.     }
  841.  
  842.     /*
  843.      * Set the positions of all children.
  844.      */
  845.     for (i = 0; i < tc->tree.n_children; i++)
  846.       set_positions (tw, tc->tree.children[i], level + 1);
  847.     }
  848. }
  849.  
  850.  
  851. static void arrange_subtree (tree, w, depth, x, y)
  852.     TreeWidget tree;
  853.     Widget w;
  854.     int depth;
  855.     Position x, y;
  856. {
  857.     TreeConstraints tc = TREE_CONSTRAINT(w);  /* info attached to all kids */
  858.     TreeConstraints firstcc, lastcc;
  859.     register int i;
  860.     int newx, newy;
  861.     Bool horiz = IsHorizontal (tree);
  862.     Widget child = NULL;
  863.     Dimension tmp;
  864.     Dimension bw2 = w->core.border_width * 2;
  865.     Bool relayout = True;
  866.  
  867.  
  868.     /*
  869.      * If no children, then just lay out where requested.
  870.      */
  871.     tc->tree.x = x;
  872.     tc->tree.y = y;
  873.  
  874.     if (horiz) {
  875.     int myh = (w->core.height + bw2);
  876.  
  877.     if (myh > (int)tc->tree.bbsubheight) {
  878.         y += (myh - (int)tc->tree.bbsubheight) / 2;
  879.         relayout = False;
  880.     }
  881.     } else {
  882.     int myw = (w->core.width + bw2);
  883.  
  884.     if (myw > (int)tc->tree.bbsubwidth) {
  885.         x += (myw - (int)tc->tree.bbsubwidth) / 2;
  886.         relayout = False;
  887.     }
  888.     }
  889.  
  890.     if ((tmp = ((Dimension) x) + tc->tree.bbwidth) > tree->tree.maxwidth)
  891.       tree->tree.maxwidth = tmp;
  892.     if ((tmp = ((Dimension) y) + tc->tree.bbheight) > tree->tree.maxheight)
  893.       tree->tree.maxheight = tmp;
  894.  
  895.     if (tc->tree.n_children == 0) return;
  896.  
  897.  
  898.     /*
  899.      * Have children, so walk down tree laying out children, then laying
  900.      * out parents.
  901.      */
  902.     if (horiz) {
  903.     newx = x + tree->tree.largest[depth];
  904.     if (depth > 0) newx += tree->tree.hpad;
  905.     newy = y;
  906.     } else {
  907.     newx = x;
  908.     newy = y + tree->tree.largest[depth];
  909.     if (depth > 0) newy += tree->tree.vpad;
  910.     }
  911.  
  912.     for (i = 0; i < tc->tree.n_children; i++) {
  913.     TreeConstraints cc;
  914.  
  915.     child = tc->tree.children[i];    /* last value is used outside loop */
  916.     cc = TREE_CONSTRAINT(child);
  917.  
  918.     arrange_subtree (tree, child, depth + 1, newx, newy);
  919.     if (horiz) {
  920.         newy += tree->tree.vpad + cc->tree.bbheight;
  921.     } else {
  922.         newx += tree->tree.hpad + cc->tree.bbwidth;
  923.     }
  924.     }
  925.  
  926.     /*
  927.      * now layout parent between first and last children
  928.      */
  929.     if (relayout) {
  930.     Position adjusted;
  931.     firstcc = TREE_CONSTRAINT (tc->tree.children[0]);
  932.     lastcc = TREE_CONSTRAINT (child);
  933.  
  934.     /* Adjustments are disallowed if they result in a position above
  935.          * or to the left of the originally requested position, because
  936.      * this could collide with the position of the previous sibling.
  937.      */
  938.     if (horiz) {
  939.         tc->tree.x = x;
  940.         adjusted = firstcc->tree.y +
  941.           ((lastcc->tree.y + (Position) child->core.height + 
  942.         (Position) child->core.border_width * 2 -
  943.         firstcc->tree.y - (Position) w->core.height - 
  944.         (Position) w->core.border_width * 2 + 1) / 2);
  945.         if (adjusted > tc->tree.y) tc->tree.y = adjusted;
  946.     } else {
  947.         adjusted = firstcc->tree.x +
  948.           ((lastcc->tree.x + (Position) child->core.width +
  949.         (Position) child->core.border_width * 2 -
  950.         firstcc->tree.x - (Position) w->core.width -
  951.         (Position) w->core.border_width * 2 + 1) / 2);
  952.         if (adjusted > tc->tree.x) tc->tree.x = adjusted;
  953.         tc->tree.y = y;
  954.     }
  955.     }
  956. }
  957.  
  958. static void set_tree_size (tw, insetvalues, width, height)
  959.     TreeWidget tw;
  960.     Boolean insetvalues;
  961.     Dimension width, height;
  962. {
  963.     if (insetvalues) {
  964.     tw->core.width = width;
  965.     tw->core.height = height;
  966.     } else {
  967.     Dimension replyWidth = 0, replyHeight = 0;
  968.     XtGeometryResult result = XtMakeResizeRequest ((Widget) tw,
  969.                                width, height,
  970.                                &replyWidth,
  971.                                &replyHeight);
  972.     /*
  973.      * Accept any compromise.
  974.      */
  975.     if (result == XtGeometryAlmost)
  976.       XtMakeResizeRequest ((Widget) tw, replyWidth, replyHeight,
  977.                    (Dimension *) NULL, (Dimension *) NULL);
  978.     }
  979.     return;
  980. }
  981.  
  982. static void layout_tree (tw, insetvalues)
  983.     TreeWidget tw;
  984.     Boolean insetvalues;
  985. {
  986.     int i;
  987.     Dimension *dp;
  988.  
  989.     /*
  990.      * Do a depth-first search computing the width and height of the bounding
  991.      * box for the tree at that position (and below).  Then, walk again using
  992.      * this information to layout the children at each level.
  993.      */
  994.  
  995.     if (tw->tree.tree_root == NULL)
  996.     return;
  997.  
  998.     tw->tree.maxwidth = tw->tree.maxheight = 0;
  999.     for (i = 0, dp = tw->tree.largest; i < tw->tree.n_largest; i++, dp++)
  1000.       *dp = 0;
  1001.     initialize_dimensions (&tw->tree.largest, &tw->tree.n_largest, 
  1002.                tw->tree.n_largest);
  1003.     compute_bounding_box_subtree (tw, tw->tree.tree_root, 0);
  1004.  
  1005.    /*
  1006.     * Second pass to do final layout.  Each child's bounding box is stacked
  1007.     * on top of (if horizontal, else next to) on top of its siblings.  The
  1008.     * parent is centered between the first and last children.
  1009.     */
  1010.     arrange_subtree (tw, tw->tree.tree_root, 0, 0, 0);
  1011.  
  1012.     /*
  1013.      * Move each widget into place.
  1014.      */
  1015.     set_tree_size (tw, insetvalues, tw->tree.maxwidth, tw->tree.maxheight);
  1016.     set_positions (tw, tw->tree.tree_root, 0);
  1017.  
  1018.     /*
  1019.      * And redisplay.
  1020.      */
  1021.     if (XtIsRealized ((Widget) tw)) {
  1022.     XClearArea (XtDisplay(tw), XtWindow((Widget)tw), 0, 0, 0, 0, True);
  1023.     }
  1024. }
  1025.  
  1026.  
  1027.  
  1028. /*****************************************************************************
  1029.  *                                                                           *
  1030.  *                 Public Routines                              *
  1031.  *                                                                           *
  1032.  *****************************************************************************/
  1033.  
  1034. void
  1035. #if NeedFunctionPrototypes
  1036. TreeForceLayout (Widget tree)
  1037. #else
  1038. TreeForceLayout (tree)
  1039.     Widget tree;
  1040. #endif
  1041. {
  1042.     layout_tree ((TreeWidget) tree, FALSE);
  1043. }
  1044.  
  1045.  
  1046.